Search for: All records

The C++ Standard Library is a valuable collection of generic algorithms and data structures that improves the usability and reliability of C++ software. Graph algorithms and data structures are notably absent from the standard library, and previous attempts to fill this gap have not gained widespread adoption. In this paper we show that the richness of graph algorithms and data structures can in fact be captured by straightforward composition of existing C++ mechanisms. Generic programming is algorithm-oriented. Accordingly, we apply a systematic approach to analyzing a broad set of graph algorithms, "lift" unnecessary constraints from them, and organize the resulting set of minimal common type requirements, i.e., concepts, for defining their interfaces. By using the newly available ranges and concepts in C++20, the type requirements for generic graph algorithms can be succinctly expressed. The generic algorithms and data structures resulting from our analysis are realized in NWGraph, a modern, composable, and extensible C++ library. 

Cities can host significant biological diversity. Yet, urbanisation leads to the loss of habitats, species, and functional groups. Understanding how multiple taxa respond to urbanisation globally is essential to promote and conserve biodiversity in cities. Using a dataset encompassing six terrestrial faunal taxa (amphibians, bats, bees, birds, carabid beetles and reptiles) across 379 cities on 6 continents, we show that urbanisation produces taxon-specific changes in trait composition, with traits related to reproductive strategy showing the strongest response. Our findings suggest that urbanisation results in four trait syndromes (mobile generalists, site specialists, central place foragers, and mobile specialists), with resources associated with reproduction and diet likely driving patterns in traits associated with mobility and body size. Functional diversity measures showed varied responses, leading to shifts in trait space likely driven by critical resource distribution and abundance, and taxon-specific trait syndromes. Maximising opportunities to support taxa with different urban trait syndromes should be pivotal in conservation and management programmes within and among cities. This will reduce the likelihood of biotic homogenisation and helps ensure that urban environments have the capacity to respond to future challenges. These actions are critical to reframe the role of cities in global biodiversity loss.

 

The GraphBLAS standard (GraphBlas.org) is being developed to bring the potential of matrix-based graph algorithms to the broadest possible audience. Mathematically, the GraphBLAS defines a core set of matrix-based graph operations that can be used to implement a wide class of graph algorithms in a wide range of programming environments. This paper provides an introduction to the mathematics of the GraphBLAS. Graphs represent connections between vertices with edges. Matrices can represent a wide range of graphs using adjacency matrices or incidence matrices. Adjacency matrices are often easier to analyze while incidence matrices are often better for representing data. Fortunately, the two are easily connected by matrix multiplication. A key feature of matrix mathematics is that a very small number of matrix operations can be used to manipulate a very wide range of graphs. This composability of a small number of operations is the foundation of the GraphBLAS. A standard such as the GraphBLAS can only be effective if it has low performance overhead. Performance measurements of prototype GraphBLAS implementations indicate that the overhead is low.